package dynamic;

import java.util.List;

public class TriangleMinimumPathSum {
    //120. 三角形最小路径和
    public int minimumTotal(List<List<Integer>> triangle) {

        for (int i = 1; i < triangle.size(); i++) {
            triangle.get(i).set(0, triangle.get(i - 1).get(0) + triangle.get(i).get(0));
        }
        int minNum = triangle.get(triangle.size() - 1).get(0);
        for (int i = 1; i < triangle.size(); i++) {
            for (int j = 1; j < triangle.get(i).size(); j++) {
                if (j < triangle.get(i).size() - 1)
                    triangle.get(i).set(j, minValue(triangle.get(i).get(j) + triangle.get(i - 1).get(j - 1), triangle.get(i).get(j) + triangle.get(i - 1).get(j)));
                else
                    triangle.get(i).set(j, triangle.get(i).get(j) + triangle.get(i - 1).get(j - 1));
            }
        }
        for (int j = 1; j < triangle.get(triangle.size() - 1).size(); j++) {
            minNum = minValue(minNum, triangle.get(triangle.size() - 1).get(j));
        }
        return minNum;
    }

    public int minValue(int a1, int a2) {
        return a1 < a2 ? a1 : a2;
    }
}
